/* 
 * Edit Distance
 */

#include "../func.h"

int minDistance (string &word1, string &word2) {
    size_t n = word1.size();
    size_t m = word2.size();

    int f[n+1][m+1];
    for (size_t i = 0; i <= n; ++i)
        f[i][0] = i;

    for (size_t j = 0; j <= m; ++j)
        f[0][j] = j;

    for (size_t i = 1; i <= n; ++i) {
        for (size_t j = 1; j <= m; ++j) {
            if (word1[i-1] == word2[j-1])
                f[i][j] = f[i-1][j-1];
            else 
            {
                int mn = min(f[i-1][j], f[i][j-1]);
                f[i][j] = 1 + min(f[i-1][j-1], mn);
            }
        }
    }
    return f[n][m];
}